Igazoljuk tehát, hogy az alábbi szabályok ( S a kezdőszimbólum, a nyelvtan többi része értelemszerű ) az L = { aibici | i >=1 } nyelvet generálják. Jelölje G a nyelvtant, azaz az állítás: L = L (G). S --> aSBC bB --> bb S --> abC bC --> bc CB --> BC cC --> cc A bizonyítás két részből áll. 1. L része L (G) -nek, azaz minden L-beli szó generálható G -vel. Választunk egy tetszőleges k-t és megmutatjuk, hogy az akbkck szó generálható G -vel. Ha k=1, a második majd a hatodik szabályt használva készen vagyunk. Ha k>1, a következőt tehetjük. Használjuk k-1 -szer egymás után az első szabályt, majd a másodikat egyszer, majd a harmadikat annyiszor amíg meg nem kapjuk az akBkCk szót (ez előbb vagy utóbb sikerülni fog, mindenesetre a dolog lehetséges). Ezután következzen a negyedik szabály k-1 -szer, az ötödik szabály egyszer, majd a hatodik szabály ismét k-1 -szer. 2. L (G) része L -nek, azaz minden G -vel generálható szó L -beli. Vizsgáljuk meg a G szabályaival végezhető levezetéseket. A kezdőszimbólum S, az első lépésben tehát vagy az első vagy a második szabály használható. A második szabály használata után csak az ötödik következhet, ami abc-t, egy L-beli szót eredményez. Ha az első szabályt használtuk, akkor a generált mondatforma tartalmazza az S szimbólumot. A levezetés következő szakaszában bizonyos számú lépésen keresztül S jelen van a mondatformában. Amíg ez a szakasz tart addig csak az első, a harmadik, vagy a szakasz utolsó lépésében a második szabály alkalmazható (a második szabály hatására ugyanis eltűnik az S szimbólum). A negyedik, ötödik vagy hatodik szabály ebben a szakaszban biztos nem alkalmazható, mivel b és c még nem keletkezhetett. Ennek a bizonyos első szakasznak a végén tehát egy olyan mondatformát kaphatunk, amely mondjuk k darab a betűvel kezdődik, egy darab b betűvel folytatódik, majd egy olyan szimbólumsorozattal végződik, ami k-1 darab B és k darab C szimbólumot tartalmaz, általunk ismeretlen sorrendben. Ekkor kezdődik a levezetés második, egyben befejező szakasza. Ebben a szakaszban az első és a második szabály nem használható, illetve a mondatforma mindvégig megőrzi azt a tulajdonságát, hogy a terminális és nemterminális szimbólumok nem keverednek, azaz egy nemterminális szimbólumtól jobbra nem állhat terminális. Ez látható, ha tudjuk, hogy az első szakasz végén a fenti tulajdonság teljesül és megvizsgáljuk az alkalmazható szabályokat: ezek segítségével nem kerülhet terminális szimbólum nemterminális szimbólumtól jobbra, amennyiben azelőtt nem volt ott. Vegyük észre, hogy ha az ötödik szabályt olyankor használjuk, amikor a szó jobboldali nemterminális része tartalmaz B szimbólumot is, a levezetést zsákutcába visszük, azaz ezután nem kaphatunk pusztán terminálisokból álló mondatformát. Ez az észrevétel következik a negyedik, ötödik és hatodik szabály alakjából illetve a bekezdés elején megfogalmazott tulajdonságból. Ha a levezetés második szakaszával kapcsolatos meggondolásokat mind figyelembe veszzük, látható, hogy vagy kapunk egy L beli terminális szót, vagy kapunk egy olyan mondatformát ami nemterminális szimbólumokat is tartalmaz, de rá a hat szabály közül egyik sem alkalmazható. Q.E.D.